/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.Stack;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a binary tree, return the postorder traversal of its
 *              nodes' values.
 * 
 *              Note: Recursive solution is trivial, could you do it
 *              iteratively?
 */
public class BinaryTreePostorderTraversal {

	private class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public ArrayList<Integer> postorderTraversal(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<>();
		if (root == null)
			return res;
		Stack<TreeNode> stack = new Stack<>();
		TreeNode pre = null;
		TreeNode cur = null;
		stack.push(root);
		while (!stack.isEmpty()) {
			cur = stack.peek();
			if (pre == null || (pre != null && (pre.left == cur || pre.right == cur))) {
				if (cur.left != null)
					stack.push(cur.left);
				else if (cur.right != null) 
					stack.push(cur.right);
			} else if (cur.left == pre) {
				if (cur.right != null)
					stack.push(cur.right);
			} else// if (pre == cur)
				res.add(stack.pop().val);
			pre = cur;
		}
		return res;
	}

	@Test
	public void test() {
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		TreeNode n6 = new TreeNode(6);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n4.left = n5;
		n4.right = n6;
		
		ArrayList<Integer> res = postorderTraversal(n1);
		for (int i : res) {
			System.out.println(i);
		}
	}
}
